|
In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. It supports two useful operations: * ''Find'': Determine which subset a particular element is in. ''Find'' typically returns an item from this set that serves as its "representative"; by comparing the result of two ''Find'' operations, one can determine whether two elements are in the same subset. * ''Union'': Join two subsets into a single subset. The other important operation, ''MakeSet'', which makes a set containing only a given element (a singleton), is generally trivial. With these three operations, many practical partitioning problems can be solved (see the ''Applications'' section). In order to define these operations more precisely, some way of representing the sets is needed. One common approach is to select a fixed element of each set, called its ''representative'', to represent the set as a whole. Then, ''Find''(x) returns the representative of the set that ''x'' belongs to, and ''Union'' takes two set representatives as its arguments. == Disjoint-set linked lists == A simple disjoint-set data structure uses a linked list for each set. The element at the head of each list is chosen as its representative. ''MakeSet'' creates a list of one element. ''Union'' appends the two lists, a constant-time operation if the list carries a pointer to its tail. The drawback of this implementation is that ''Find'' requires O(''n'') or linear time to traverse the list backwards from a given element to the head of the list. This can be avoided by including in each linked list node a pointer to the head of the list; then ''Find'' takes constant time, since this pointer refers directly to the set representative. However, ''Union'' now has to update each element of the list being appended to make it point to the head of the new combined list, requiring Ω(''n'') time. When the length of each list is tracked, the required time can be improved by always appending the smaller list to the longer. Using this ''weighted-union heuristic'', a sequence of ''m'' ''MakeSet'', ''Union'', and ''Find'' operations on ''n'' elements requires O(''m'' + ''n''log ''n'') time. For asymptotically faster operations, a different data structure is needed. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Disjoint-set data structure」の詳細全文を読む スポンサード リンク
|